//
// Created by gyc on 2020/9/23.
//
/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 *
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 */
#include "../../common.h"


class Solution {

public:

    int search(vector<int> &nums, int target, int compare) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = (left + ((right - right) >> 1));
            if (target < nums[mid]) {
                right = mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                if (compare > 0) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        if (compare > 0) {
            return (left > 0 && target == nums[left - 1]) ? left - 1 : -1;
        } else {
            return (right < nums.size() && target == nums[right]) ? right : -1;
        }
    }


    vector<int> searchRange(vector<int> &nums, int target) {
        if (nums.empty()) {
            return {-1, -1};
        }
        int left = search(nums, target, -1);
        int right = search(nums, target, 1);
        return {left, right};
    }
};

int main() {

    // [-1,0,3,5,9,12]
    //2

    vector<int> vec{1};
    auto v = Solution().searchRange(vec, 0);
    cout << v[0] << v[1] << endl;
}